<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      var findItinerary = function (tickets) {
        const map = new Map()
        let res = ['JFK']
        for (let [from, to] of tickets) {
          if (!map.has(from)) {
            map.set(from, [])
          }
          map.get(from).push(to)
        }
        for (let [key, value] of map) {
          value.sort()
        }

        function backTracking() {
          if (res.length == tickets.length + 1) {
            return true
          }
          //机票未用完
          let nextCities = map.get(res[res.length - 1])
          if (!nextCities || !nextCities.length) return false
          for (let i = 0; i < nextCities.length; i++) {
            let nextCity = nextCities[i]
            res.push(nextCity)
            nextCities.splice(i, 1)
            if (backTracking()) {
              return true
            } else {
              res.pop()
              nextCities.splice(i, 0, nextCity)
            }
          }
        }
        backTracking()
        return res
      }
    </script>
  </body>
</html>
